//
// Description: 97. 交错字符串
// Created by Loading on 2022/6/15.
//

#include <bits/stdc++.h>

using namespace std;

bool isInterleave(string s1, string s2, string s3) {
    int n = s1.size();
    int m = s2.size();
    if (n + m != s3.size()) {
        return false;
    }

    // 空间优化版dp
    bool dp[m + 1];
    memset(dp, false, sizeof dp);
    dp[0] = true;

    for (int i = 1; i <= m; ++i) {
        if (s2[i - 1] == s3[i - 1]) {
            dp[i] = true;
        } else {
            break;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[j] &= s3[i + j - 1] == s1[i - 1];
            if (j > 0 && s3[i + j - 1] == s2[j - 1]) {
                dp[j] |= dp[j - 1];
            }
        }
    }

    return dp[m];
}

int main() {
    string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";

    auto res = isInterleave(s1, s2, s3);

    cout << res << endl;

    return 0;
}